//给定一个二叉树，判断它是否是高度平衡的二叉树。 
//
// 本题中，一棵高度平衡二叉树定义为： 
//
// 
// 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 
// 
//
// 示例 1: 
//
// 给定二叉树 [3,9,20,null,null,15,7] 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7 
//
// 返回 true 。 
// 
//示例 2: 
//
// 给定二叉树 [1,2,2,3,3,null,null,4,4] 
//
//        1
//      / \
//     2   2
//    / \
//   3   3
//  / \
// 4   4
// 
//
// 返回 false 。 
//
// 
// Related Topics 树 深度优先搜索 
// 👍 384 👎 0

package leetcode.editor.cn;

import java.util.Map;

//Java：平衡二叉树
public class P110BalancedBinaryTree {
    public static void main(String[] args) {
        Solution solution = new P110BalancedBinaryTree().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) { val = x;
        }

    }
    class Solution {

        /*
         * 时间复杂度为O(n^2)的解法
         * 遍历每个结点时间复杂度为O(n)
         * 然后又计算其左右子树的高度也为O(n)
         * 因此最后时间复杂度为O(n^2)
         * */
        private boolean result=true;
        public boolean isBalanced(TreeNode root) {
            if(root==null){
                return true;
            }
           // return isBalanced1(root.left)&&isBalanced1(root.right)&& Math.abs(getLevel(root.left)-getLevel(root.right))<=1;
            getLevel(root);
            return result;
        }

        public int getLevel(TreeNode root){
            if(root==null){
                return 0;
            }
            int left=getLevel(root.left);
            int right=getLevel(root.right);
            if(Math.abs(left-right)>1){
                result=false;
            }
            return Math.max(left,right)+1;
            //return Math.max(getLevel(root.left),getLevel(root.right))+1;
        }


        /*
        * 使用自底向上，也就是后序遍历的方法
        *
        * */
        public boolean res=true;
        public boolean isBalanced1(TreeNode root) {
            if(root==null){
                return true;
            }

            postOrder(root);
            return res;
        }

        public int postOrder(TreeNode root){
            if(root==null){
                return 0;
            }
            int L=1+postOrder(root.left);
            int R=1+postOrder(root.right);
            if(Math.abs(L-R)>1){
                res=false;
            }

            return Math.max(L,R);
        }



    }
//leetcode submit region end(Prohibit modification and deletion)

}
